package com.promote.sort;

import java.util.HashSet;
import java.util.Set;

/**
 * @ClassName LongestSubstring
 * Description 无重复字符的最长子串
 * @Author lizihao
 * Date 2021/4/9 11:20
 * @Version 1.0
 **/
public class LongestSubstring {

    public static void main(String[] args) {

        String s = "abcdcdbafafa";
        int length = lengthLongestSubstring(s);

        System.out.println(length);
    }

    public static int lengthLongestSubstring(String s) {
        //哈希集合，记录每个字符是否出现
        Set<Character> hashSet = new HashSet<>();

        int length = s.length();

        int rk = -1, ans = 0;

        for (int i = 0; i < length; ++i) {
            if (i != 0) {

                hashSet.remove(s.charAt(i-1));
            }
            while (rk + 1 < length && !hashSet.contains(s.charAt(rk+1))) {
                //不断移动右指针
                hashSet.add(s.charAt(rk+1));
                ++rk;
            }
            ans = Math.max(ans, rk-i+1);
        }
        return ans;
    }
}
